package CS331Lab3;

public class DList<E extends Comparable<E>> {

	   private class Node {
		      public E data;
		      public Node next;
		      public Node prev;

		      public Node(E data) {
		         this.data = data;
		      }

		      public Node(Node newPrev,E data,Node newNext) {
		         this.data = data;
		         this.prev = newPrev;
		         this.next = newNext;
		      }
		   }

	   private int size;
	   private Node sentinel;
	   
	   public DList() {
		   size = 0;
		   sentinel = new Node(null, null, null);
		   sentinel.next = sentinel;
		   sentinel.prev = sentinel;
	   }
	   
	   public int size() {
		   return size;
	   }
	   
	   public void insertFront(E data) {
		   sentinel.next.prev = new Node(sentinel, data, sentinel.next);
		   sentinel.next = sentinel.next.prev;
		   size++;
	   }
	   
	   public void insertEnd(E data) {
		   sentinel.prev.next = new Node(sentinel.prev, data, sentinel);
		   sentinel.prev = sentinel.prev.next;
		   size++;
	   }
	   
	   public void deleteFront() {
		   if(sentinel.next != sentinel) {
			   sentinel.next.next.prev = sentinel;
			   sentinel.next = sentinel.next.next;
			   size--;
		   }
	   }
	   
	   public void deleteEnd() {
		   if(sentinel.prev != sentinel) {
			   sentinel.prev.prev = sentinel;
			   sentinel.prev = sentinel.prev.prev;
			   size--;
		   }
	   }
	   
	   private abstract class AllIterator implements Iterator<E> {
		   protected Node cursor;
		   protected boolean valid;
		   
		   public E get() {
			   if(cursor != sentinel && cursor != null)
				   return cursor.data;
			   else
				   return null;
		   }
		   
		   public boolean isValid() {
			   return valid;
		   }
		   
		   public abstract void next();
		   
		   public void delete() {
			   //your code here!
			   //what are the boundary conditions?
			   if(cursor != sentinel) {
				    cursor.prev.next = cursor.next;
					cursor.next.prev = cursor.prev;
					cursor = cursor.next;
					size--;
			   }
			   if(cursor == sentinel) {
				   valid = false;
			   }
		   }
	   }
	   
	   public class makeFwdIterator extends AllIterator {
		   
		   public makeFwdIterator() {
			   cursor = sentinel;
			   this.next();
			   if(cursor != sentinel)
				   valid = true;
		   }
		   
		   public void next() {
			   if(cursor.next != sentinel)
				   cursor = cursor.next;
			   else{
				   cursor = null;
				   valid = false;
			   }
		   }
	   }
	   
	   public class makeRevIterator extends AllIterator {
		   
		   public makeRevIterator() {
			   cursor = sentinel;
			   this.next();
			   if(cursor != sentinel)
				   valid = true;
		   }
		   
		   public void next() {
			   if(cursor.prev != sentinel)
				   cursor = cursor.prev;
			   else {
				   cursor = null;
				   valid = false;
			   }
		   }
	   }
	   
	   public class makeFwdFindIterator extends makeFwdIterator {
		   
		   public makeFwdFindIterator() {
			   super();
		   }
		   
		   public int next(E query) {
			   while(cursor != sentinel) {
				   if(cursor.data.compareTo(query) == 0) {
					   cursor = sentinel;
					   super.next();
					   return 1;
				   }
				   else
					   cursor = cursor.next;
			   }
			   cursor = sentinel;
			   super.next();
			   return 0;
		   }
	   }
	   
	   public class makeRevFindIterator extends makeRevIterator {
		   
		   public makeRevFindIterator() {
			   super();
		   }
		   
		   public int next(E query) {
			   	while(cursor != sentinel) {
			   		if(cursor.data.compareTo(query) == 0) {
			   			cursor = sentinel;
			   			super.next();
			   			return 1;
			   		}
			   		else
			   			cursor = cursor.prev;
			   	}
			   	cursor = sentinel;
			   	super.next();
			   	return 0;
		   }
	   }
}
